package bfs;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

import graph.Node;


public class Bfs {

	Queue<Node> q= new LinkedList<Node>();
	long maxMemory;


	public Node[] solve(Node root){
		maxMemory = 0;
		//  need somehow to clear all mark of the graph starting at g 

		Node goal = null;


		q.add(root);
		root.mark(0);

		while (!q.isEmpty() && goal==null){
			Node u = q.poll();
			Node[] u_children = u.getChildren();
			for (Node node : u_children)   {
				if (node.mark(0)){
					node.setParent(u, 0);
					if (node.isGoal()){
						goal = node;
					}
					q.add(node);
					maxMemory = Math.max(maxMemory, q.size());
				}
			}
		}


		if (goal == null) return null; // need to fix in case the root is the goal.
		Vector<Node> solution = new Vector<Node>();

		for (Node n=goal; n!=null; n=n.getParent()){
			solution.add(n);
		}
		Node[] result = new Node[solution.size()];
		for (int i=0; i<result.length; i++){
			result[result.length-1-i] = solution.get(i);
		}
		return result;
	}
	
	public long getMaxMemory() {
		return maxMemory;
	}

}
